#include <bits/stdc++.h>

using namespace std;

class Solution
{
public:
    int maximalRectangle(vector<vector<char>> &matrix)
    {
        if (matrix.empty()) return 0;
        int n = matrix.size(), m = matrix[0].size();
        vector<int> height(m, 0);
        int res = 0;

        for (int i = 0; i < n; ++i)
        {
            for (int j = 0; j < m; ++j)
            {
                height[j] = matrix[i][j] == '1' ? height[j] + 1 : 0;
            }
            res = max(res, largestRectangleArea(height));
        }

        return res;
    }

private:
    int largestRectangleArea(vector<int> &heights)
    {
        stack<int> s;
        heights.push_back(0);
        int maxArea = 0;

        for (int i = 0; i < heights.size(); ++i)
        {
            while (!s.empty() && heights[i] < heights[s.top()])
            {
                int h = heights[s.top()];
                s.pop();
                int w = s.empty() ? i : i - s.top() - 1;
                maxArea = max(maxArea, h * w);
            }
            s.push(i);
        }

        heights.pop_back();
        return maxArea;
    }
};

int main()
{
    vector<vector<char>> matrix = {
        {'1', '0', '1', '0', '0'},
        {'1', '0', '1', '1', '1'},
        {'1', '1', '1', '1', '1'},
        {'1', '0', '0', '1', '0'}
    };

    Solution sol;
    cout << sol.maximalRectangle(matrix) << endl;

    return 0;
}